
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * A class representing a Sokoban board in a manner suitable for fast AI operations.
 */
public class Board {
	
	/** A map of the tiles on which players can walk and/or boxes can be placed. */
	public boolean[][] floor;
	
	/** A map of the tiles on which boxes can be placed without loosing the game. */
	public boolean[][] safeTiles;
	
	
	/** An array containing the coordinates of all targets */
	public Pos[] targets;

	/** The position of the player */
	public Pos player;

	/** A map of the tiles where boxes are placed */
	public boolean[][] boxmap = null;

	/** An array containing the coordinates of all boxes
	 * This is generated from {@link #boxmap} by {@link #calculateMaps()}. */
	public Pos[] boxes; // derived from boxmap

	/** A map of the tiles where targets are placed, allowing for faster lookups.
	 * This is generated from {@link #targets} by {@link #calculateMaps()}. */
	public boolean[][] targetmap = null; // derived from targets

	/** A map of the tiles the player can reach without moving boxes.
	 * This is generated by {@link #calculateMaps()}
	 * from {@link #floor} and {@link #boxmap}*/
	public boolean[][] reachable = null; // derived from floor, boxes and player

	/** caches the distance sum once calculated,  see {@link #distanceSum()}*/
	private Integer distsum = null;
	
	/** caches the simple distance sum once calculated,  see {@link #simpleDistanceSum()}*/
	private Integer simpleDistSum = null;

	
	/** A array of maps - each map stores the shortest-path distances to a specific target.
	 * Walls are taken into account! */
	private int[][][] distanceMaps = null;
	
	public Board(int width, int height, int boxCount) {
		if (width > 125 || height > 125 || boxCount > 125) throw new RuntimeException("Too large board or too many boxes");
		
		this.floor = new boolean[width][height];
		this.boxmap = new boolean[width][height];
		this.targets = new Pos[boxCount];
	}
	
	/**
	 * Calculates and sets the box and reachable tile maps. 
	 */
	public void calculateMaps() {	
		if (targetmap == null) {
			targetmap = new boolean[floor.length][floor[0].length]; // auto-initializes to false
			for (Pos p : targets) {
				targetmap[p.x][p.y] = true;
			}		
		}

		if (distanceMaps == null) {
			calcDistanceMaps();
		}
		
		calcBoxMap();
		
		if (safeTiles == null) {
			calcSafeTiles();
		}

		reachable = new boolean[floor.length][floor[0].length]; // auto-initializes to false
		addReachable(player.x, player.y);
	}
	
	/** Calculates the distance maps for all targets */
	private void calcDistanceMaps() {
		distanceMaps = new int[targets.length][][];
		for (int i = 0; i< targets.length; i++) {
			distanceMaps[i] = calcDistanceMap(i);
		}
	}
	
	/**
	 * Calculates the distance map for a specific target using BFS
	 * @param targetNumber the number of the target for which the map should be created
	 */
	private int[][] calcDistanceMap(int targetNumber) {
		int[][] distmap = new int[floor.length][floor[0].length];
		LinkedList<Pos> toExpand = new LinkedList<Pos>();
		
		// initialize
		for (int x = 0; x < distmap.length; x++) {
			for (int y = 0; y < distmap[0].length; y++) {
				distmap[x][y] = Integer.MAX_VALUE;
			}
		}
		
		toExpand.add(targets[targetNumber]);
		distmap[targets[targetNumber].x][targets[targetNumber].y] = 0;
		
		while (!toExpand.isEmpty()) {
			Pos curr = toExpand.pop();
			int nextDist = distmap[curr.x][curr.y]+1;

			// handle neighbors
			if (floor[curr.x-1][curr.y] && distmap[curr.x-1][curr.y] == Integer.MAX_VALUE) {
				distmap[curr.x-1][curr.y] = nextDist;
				toExpand.add(new Pos((byte)(curr.x-1),curr.y));
			}
			if (floor[curr.x+1][curr.y] && distmap[curr.x+1][curr.y] == Integer.MAX_VALUE) {
				distmap[curr.x+1][curr.y] = nextDist;
				toExpand.add(new Pos((byte)(curr.x+1),curr.y));
			}
			if (floor[curr.x][curr.y-1] && distmap[curr.x][curr.y-1] == Integer.MAX_VALUE) {
				distmap[curr.x][curr.y-1] = nextDist;
				toExpand.add(new Pos(curr.x,(byte)(curr.y-1)));
			}
			if (floor[curr.x][curr.y+1] && distmap[curr.x][curr.y+1] == Integer.MAX_VALUE) {
				distmap[curr.x][curr.y+1] = nextDist;
				toExpand.add(new Pos(curr.x,(byte)(curr.y+1)));
			}
		}
		
		//System.out.println("Distance map for target " + targetNumber);
		//printMap(distmap);
		
		return distmap;
	}

	private void calcBoxMap() {
		boxes = new Pos[targets.length];
		int storeBoxAt = 0;
		for (byte x = 0; x < boxmap.length; x++) {
			for (byte y = 0; y < boxmap[0].length; y++) {
				if (boxmap[x][y]) {
					boxes[storeBoxAt++] = new Pos(x,y);
				}
			}
		}
		
		assert(storeBoxAt == boxes.length);
	}
	
	/**
	 * Calculates the safe tile map. Requires target map!
	 */
	private void calcSafeTiles() {
		safeTiles = new boolean[floor.length][floor[0].length]; // auto-initializes to false
		List<Pos> newSafeTiles = new LinkedList<Pos>();
		for (Pos target : targets) {
			newSafeTiles.add(target); // targets are always safe
		}
		while (!newSafeTiles.isEmpty()) {
			Pos currSafeTile = newSafeTiles.remove(0);
			if (safeTiles[currSafeTile.x][currSafeTile.y]) continue; // do not revisit!
			// actually, more work would be necessary to fully avoid that, but speed is not an issue
			// as this is only run once per board
			
			safeTiles[currSafeTile.x][currSafeTile.y] = true;
			//System.out.println("marked safe: " + currTile);

			if (floor[currSafeTile.x-1][currSafeTile.y] && floor[currSafeTile.x-2][currSafeTile.y])
				newSafeTiles.add(new Pos((byte)(currSafeTile.x-1),currSafeTile.y));
			if (floor[currSafeTile.x+1][currSafeTile.y] && floor[currSafeTile.x+2][currSafeTile.y])
				newSafeTiles.add(new Pos((byte)(currSafeTile.x+1),currSafeTile.y));
			if (floor[currSafeTile.x][currSafeTile.y-1] && floor[currSafeTile.x][currSafeTile.y-2])
				newSafeTiles.add(new Pos(currSafeTile.x,(byte)(currSafeTile.y-1)));
			if (floor[currSafeTile.x][currSafeTile.y+1] && floor[currSafeTile.x][currSafeTile.y+2])
				newSafeTiles.add(new Pos(currSafeTile.x,(byte)(currSafeTile.y+1)));
		}
		
	}

	/**
	 * Checks if the given coordinate can be stepped on. If yes, it
	 *   a) marks it as reachable and 
	 *   b) performs the check for its four direct neighbors.
	 * This allows to "flood fill" the reachable area.
	 * @param x the x coordinate of the tile to check (and maybe add) as reachable
	 * @param y the y coordinate of the tile to check (and maybe add) as reachable
	 */
	private void addReachable(int x, int y) {
		if (!reachable[x][y] && floor[x][y] && !boxmap[x][y]) {
			reachable[x][y] = true;
			addReachable(x-1,y);
			addReachable(x+1,y);
			addReachable(x,y-1);
			addReachable(x,y+1);
		}
	}
	
	/**
	 * Tests if a move is possible. Maps have to be calculated before calling this method.
	 * A move is possible if:
	 *   a) the player can reach the direction from which the box will be pushed
	 *   b) the target field is a floor tile
	 *   c) the target field is not occupied by a box
	 * @param boxID the ID of the box to be moved
	 * @param direction the direction in which the box is to be moved (1: up, 2: right, 3: down, 4: left)
	 * @return true if the move is possible
	 */
	public boolean canMove(Pos box, int direction) {
		int xdir = 0, ydir = 0;
		switch (direction) {
		case 1: xdir = 0; ydir = -1; break;
		case 2: xdir = 1; ydir = 0; break;
		case 3: xdir = 0; ydir = 1; break;
		case 4: xdir = -1; ydir = 0; break;
		default: throw new RuntimeException("Invalid direction " + direction);
		}
		
		return reachable[box.x - xdir][box.y - ydir] && // can get to pushing pos
				safeTiles[box.x+xdir][box.y+ydir] && // there is a acceptable place to push to
				!boxmap[box.x+xdir][box.y+ydir]; // and it is free
	}
	
	public List<Move> getPossibleMoves() {
		List<Move> result = new LinkedList<Move>();
		for (int box = 0; box < boxes.length; box++) {
			for (int dir = 1; dir < 5; dir++) {
				if ( canMove(boxes[box],dir) ) {
					//Calculate the distanceSum this move would generate
					Board workingBoard = this.partialClone();
					workingBoard.move(boxes[box], dir);
					workingBoard.calcBoxMap();
					int dist = workingBoard.distanceSumReal();
					//add it to the list with the distance
					result.add(new Move(boxes[box],dir,dist));
				}
			}
		}
		/**
		 * This sorts the list so that the move with the lowest distanceSum comes first.
		 * It uses a costume compare
		 */
		Collections.sort(result);
		return result;
	}
	
	/**
	 * Performs a move, changing the board. Does NOT check for invalid moves!
	 * 
	 * Maps do NOT have to be calculated before calling this method,
	 * maps that have been calculated are discarded!
	 * 
	 * This allows fast application of moves.
	 * 
	 * @see {@link #move(List)}
	 * 
	 * @param boxID the ID of the box to be moved
	 * @param direction the direction in which the box is to be moved (1: up, 2: right, 3: down, 4: left)
	 */
	public void move(Pos box, int direction) {
		int xdir = 0, ydir = 0;
		switch (direction) {
		case 1: xdir = 0; ydir = -1; break;
		case 2: xdir = 1; ydir = 0; break;
		case 3: xdir = 0; ydir = 1; break;
		case 4: xdir = -1; ydir = 0; break;
		default: throw new RuntimeException("Invalid direction " + direction);
		}
		
		player = box.clone(); // place player at the position resulting from the push
		boxmap[box.x][box.y] = false;
		boxmap[box.x+xdir][box.y+ydir] = true;
		
		// maps are invalid now, discard
		reachable = null;
		boxes = null;
		simpleDistSum = null;
	}
	
	/**
	 * Performs a list of moves, changing the board. Does NOT check for invalid moves!
	 * 
	 * Maps do NOT have to be calculated before calling this method,
	 * maps that have been calculated are discarded!
	 * 
	 * This allows fast application of many moves.
	 * 
	 * @param moveList
	 * @see {@link #move(int, int)}
	 */
	public void move(List<Move> moveList) {
		for (Move m : moveList) {
			move(m.box, m.direction);
		}
	}
	
	/**
	 * Creates an independent copy of this board, without the maps.
	 * Things that are not meant to change (floor, targets, safe tiles, ...) are shared references!
	 * @return the copy
	 */
	public Board partialClone() {
		Board result = new Board(floor.length, floor[0].length,targets.length);
		
		
		result.floor = floor;
		result.safeTiles = safeTiles;
		
		result.targets = targets;
		result.player = player.clone();

		for (int x = 0; x < boxmap.length; x++) {
			result.boxmap[x] = boxmap[x].clone();
		}

		result.targetmap = targetmap;
		result.distanceMaps = distanceMaps;
		
		return result;
	}

	/**
	 * @return The sum of the ("city-block") distances between each box and the nearest target.
	 * Does require the box and target lists, but not the reachable map
	 */
	public int simpleDistanceSum() {
		if (simpleDistSum != null ) return simpleDistSum;
		int distsum = 0;
		for (Pos box : this.boxes) {
			int mindist = Integer.MAX_VALUE;
			for (Pos target : targets) {
				int dist = box.distance(target);
				if (dist < mindist) {
					mindist = dist;
				}
			}
			distsum += mindist;
		}
		return distsum;
	}
	
	/**
	 * @return The sum of the shortest-path distances between each box and the nearest target (weighted 3x) and all targets.
	 * Does require the box and target lists and the distance map, but not the reachable map
	 */
	public int distanceSumRealWeighted() {
		if (distsum != null ) return distsum;
		int distsum = 0;
		for (Pos box : this.boxes) {
			int mindist = Integer.MAX_VALUE;
			for (int targetNumber = 0; targetNumber < targets.length; targetNumber++) {
				int dist = distanceMaps[targetNumber][box.x][box.y];
				if (dist < mindist) {
					mindist = dist;
				}
				distsum += dist;
			}
			distsum += 3 * mindist;
		}
		return distsum;
	}
	
	/**
	 * @return The sum of the shortest-path distances between each box and the nearest target
	 * Does require the box and target lists and the distance map, but not the reachable map
	 */
	public int distanceSumReal() {
		if (distsum != null ) return distsum;
		int distsum = 0;
		for (Pos box : this.boxes) {
			int mindist = Integer.MAX_VALUE;
			for (int targetNumber = 0; targetNumber < targets.length; targetNumber++) {
				int dist = distanceMaps[targetNumber][box.x][box.y];
				if (dist < mindist) {
					mindist = dist;
				}
			}
			distsum += mindist;
		}
		return distsum;
	}
	
	/**
	 * uses a simple method to assign boxes to targets (each target grabs the nearest still not grabbed box)
	 * then calculates the sum of distances
	 * @return
	 */
	public int distanceSumSimpleAssign() {
		if (distsum != null) return distsum;
		int distsum = 0;
		
		List<Pos> remainingBoxes = new LinkedList<Pos>();
		for (Pos box : boxes) remainingBoxes.add(box);
		
		for (int targetNumber = 0; targetNumber < targets.length; targetNumber++) {
			int bestindex = -1;
			int bestvalue = Integer.MAX_VALUE;
			int index = 0;
			for (Pos box : remainingBoxes) { // find nearest box
				int dist = distanceMaps[targetNumber][box.x][box.y];
				if (dist < bestvalue) {
					bestvalue = dist;
					bestindex = index;
				}
				index++;
			}
			remainingBoxes.remove(bestindex);
			distsum += bestvalue;
		}

		return distsum;
	}
	
	/** Calculates the minimal distance sum for the optimal assignment of boxes to target.
	 * uses the hungarian algorithm - too slow */
	@Deprecated
	public int distanceSumHungarian() {
		int[][] matrix = new int[boxes.length][targets.length];
		for (int boxnr = 0; boxnr < boxes.length; boxnr++) {
			for (int targetnr = 0; targetnr < targets.length; targetnr++) {
				matrix[boxnr][targetnr] = distanceMaps[targetnr][boxes[boxnr].x][boxes[boxnr].y];
			}
		}
		
		return HungarianAlgorithm.minCost(matrix);
	}
	
	/**
	 * Checks if the board is solved. Assumes that board is valid, i.e. no invalid moves have been made!
	 * Requires maps until distanceSum is fixed.
	 * @return true if the board is solved
	 */
	public boolean isSolved() {
		return simpleDistanceSum() == 0;
	}
		
	/**
	 * Checks if the board is deadlocked (i.e. cannot be won).
	 * Requires maps.
	 * @return true if the board is deadlocked
	 */
	public boolean isDeadlocked() {
		Board workBoard = this.partialClone();
		
		boolean hasRemoved = true;
		while (hasRemoved) {
			hasRemoved = false;
			workBoard.calculateMaps(); // this recalculates workBoard.boxes
			for (Pos box : workBoard.boxes) {
				if (box == null) break; // end of boxes
				if (workBoard.canMove(box, 1) || workBoard.canMove(box, 2) ||
						workBoard.canMove(box, 3) || workBoard.canMove(box, 4) ) {
					// box can move -> remove it
					hasRemoved = true;
					workBoard.boxmap[box.x][box.y] = false;
					//break; // break the for loop
				}
			}
		}
		
		// after the last box has been removed, the loop above is run again
		// this makes sure that maps are calculated
		
		for (Pos box : workBoard.boxes) {
			if (box == null) break; // end of boxes
			if (!workBoard.targetmap[box.x][box.y]) // ignore boxes on targets
				return true; // at least one box could not be moved after removing movable ones
		}
		
		return false;
	}

	/**
	 * Helper function for debugging. Prints a boolean map.
	 * @param map The map to be printed
	 * @param fg The character to be used for foreground (true) tiles.
	 * @param bg The character to be used for background (false) tiles.
	 */
	public static void printMap(boolean[][] map, char fg, char bg) {
		for (int y = 0; y < map[0].length; y++) {
			for (int x = 0; x < map.length; x++) {
				System.out.print(map[x][y] ? fg : bg);
			}
			System.out.println();
		}		
	}
	
	/**
	 * Helper function for debugging. Prints a integer map.
	 * @param map The map to be printed
	 */
	public static void printMap(int[][] map) {
		for (int y = 0; y < map[0].length; y++) {
			for (int x = 0; x < map.length; x++) {
				if (map[x][y] == Integer.MAX_VALUE) {
					System.out.print("   ");
				} else {
					System.out.print(map[x][y] > 99 ? "## " : String.format("%2d ", map[x][y]));
				}
			}
			System.out.println();
		}		
	}
	
	/**
	 * Converts the board to a multi-line string showing its current state.
	 * Maps will be calculated automatically if not already available.
	 */
	public String toString() {
		if (targetmap == null) calculateMaps();
		
		StringBuffer result = new StringBuffer();
		for (int y = 0; y < floor[0].length; y++) {
			for (int x = 0; x < floor.length; x++) {
				if (!floor[x][y]) {
					result.append("#");
					continue;
				}
				if (boxmap[x][y]) {
					if (targetmap[x][y]) {
						result.append("*");
					} else {
						result.append("$");
					}
					continue;
				}
				if (x == player.x && y == player.y) {
					if (targetmap[x][y]) {
						result.append("+");
					} else {
						result.append("@");
					}
					continue;					
				}
				// if none of the above, either target or floor
				if (targetmap[x][y]) {
					result.append(".");
				} else {
					result.append(" ");
				}
				
			}
			result.append("\n");
		}
		return result.toString();
	}
	
}
